11.6 KB · ⇊ 4 parts · ⤓ Micron 11.6 KB · ⤓ HTML 32.9 KB

top

In mwawcrittografia, le mwbaS-Box (o mwbqmwbgSubstitution-box, mwbwlett. "scatole di sostituzione") sono dei componenti base degli mwcaalgoritmi a chiave simmetrica. Nella mwcqcrittografia a blocchi le S-Box vengono utilizzate per oscurare relazioni tra il testo in chiaro e il testo cifrato seguendo il principio della mwcgconfusione enunciato da mwcwmwdaShannon. Spesso le S-Box vengono appositamente progettate per resistere alla mwdqcrittanalisi, come nel caso del mwdgDEScite-ref-1[1].

• Caratteristiche

• Esempio di S-Box

• Utilizzo nel Data Encryption Standard

• Sicurezza e crittanalisi

• Note

• Bibliografia

• Voci correlate

• Altri progetti

• Collegamenti esterni

In generale le S-Box ricevono mwfg m {\displaystyle m} bit di ingresso e li trasformano in mwfw n {\displaystyle n} bit di uscita. Una S-Box mwga n × × m {\displaystyle n\times m} può essere implementata come una mwgqlookup table di mwgg 2 m {\displaystyle 2^{m}} mwgwword di mwha n {\displaystyle n} bit l'una, che di norma sono tabelle fisse, come nel caso del DES, anche se in alcuni cifrari sono generate dinamicamente a partire dalla mwhqchiave crittografica, come nel caso del mwhgBlowfish e del mwhwTwofish. mwiaBruce Schneier descrive la moltiplicazione lineare dell'mwiqIDEA come una S-Box dipendente dalla chiave.

Questa è un esempio di matrice S-Box mwja 4 × × 16 {\displaystyle 4\times 16} del DES (mwjq S 5 {\displaystyle S_{5}} ):

| S 5 {\displaystyle S_{5}} | S 5 {\displaystyle S_{5}} | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso | 4 bit centrali in ingresso |

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

| S 5 {\displaystyle S_{5}} | S 5 {\displaystyle S_{5}} | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |

| bit esterni | 00 | 0010 | 1100 | 0100 | 0001 | 0111 | 1010 | 1011 | 0110 | 1000 | 0101 | 0011 | 1111 | 1101 | 0000 | 1110 | 1001 |

| bit esterni | 01 | 1110 | 1011 | 0010 | 1100 | 0100 | 0111 | 1101 | 0001 | 0101 | 0000 | 1111 | 1100 | 0011 | 1001 | 1000 | 0110 |

| bit esterni | 10 | 0100 | 0010 | 0001 | 1011 | 1100 | 1101 | 0111 | 1000 | 1111 | 1001 | 1100 | 0101 | 0110 | 0011 | 0000 | 1110 |

| bit esterni | 11 | 1011 | 1000 | 1100 | 0111 | 0001 | 1110 | 0010 | 1101 | 0110 | 1111 | 0000 | 1001 | 1100 | 0100 | 0101 | 0011 |

Questa S-Box ha 6 bit di ingresso e 4 in uscita. Il primo e l'ultimo bit vengono utilizzati per individuare la riga mentre i bit centrali vengono utilizzati per individuare la colonna. Per esempio il numero in ingresso mwia011011 ha agli estremi i bit mwiq01 e centralmente i bit mwig1101 che producono come uscita il valore mwiw1001.

Le S-Box utilizzate del DES sono state per anni oggetto di studi dato che si riteneva possibile che il mwjgGoverno mwjwstatunitense avesse accuratamente scelto i valori delle S-Box per poter decifrare qualsiasi messaggio tramite una particolare parola chiave che avrebbe funzionato come una chiave universale. Dopo la scoperta pubblica della mwkacrittanalisi differenziale, mwkqDon Coppersmith nel mwkg1994 pubblicò degli studi riservati sulle S-Box che dimostravano che queste erano state accuratamente progettate per resistere a quel tipo di attacco dato che gli ingegneri mwkwIBM (che progettarono il DES) erano già a conoscenza di quella tecnica di analisi decenni prima della sua "scoperta" da parte degli esperti esterni. Un altro studio dimostrò che anche una piccola modifica dei valori nelle S-Box mwlaavrebbe esposto il DES alla crittoanalisi differenziale.

Molte ricerche sono state svolte sulle S-Box e si è scoperto molto sulle loro proprietà e sulle tecniche per sviluppare delle buone S-Box.

Talune ricerchecite-ref-2[2] di mwnaDaniel J. Bernstein hanno dimostrato come la classica implementazione software delle S-Box, ovvero l'uso di mwnqarray pre-calcolato di valori, sia in realtà vulnerabile ad attacchi basati sul tempo: difatti per vari motivi (in primis la dimensione limitata delle mwnwcache delle mwoaCPU) difficilmente l'intero array avrà tempi di accesso omogenei. Utilizzando questa tecnica ha sviluppato un programma dimostrativo che recupera una chiave mwoqAES da un'altra macchina in rete locale in poche ore e senza utilizzare alcuna informazione sui dati cifrati stessi. Bisogna ancora capire quanto questo si ripercuoterà sull'utilità stessa di utilizzo delle S-Box, spesso usate proprio perché l'accesso ad un array pre-calcolato è sempre stato considerato sia efficiente che tempo-costante.

cite-note-11. ↑ mwqa(mwqqmwqgENmwqw) mwraBruce Schneier, mwrqApplied Cryptography, 2ªmwrg ed., John Wiley & Sons, 1996, p.mwrw 280, mwsaISBNmwsq 0-471-12845-7.

cite-note-22. ↑ mwtw(mwuamwuqENmwug) mwuw (mwvamwvqPDFmwvg) mwvwCache-timing attacks on AES - Daniel J. Bernstein

• mwwwKaisa Nyberg, Perfect nonlinear S-boxes (PDF), Advances in Cryptology - EUROCRYPT '91, Brighton, 1991, pp. 378-386. URL consultato il 20 febbraio 2007 (archiviato dall'url originale il 26 settembre 2007).

• mwxgDon Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, in IBM Journal of Research and Development, vol. 38, n. 3, 1994, pp. 243-250.

• mwyaS. Mister and C. Adams, Practical S-Box Design (ps), Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record, Queens University, 1996, pp. 61-76. URL consultato il 20 febbraio 2007 (archiviato dall'url originale il 31 agosto 2006).

• mwygBruce Schneier, Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, 1996, pp. 296-298, 349, ISBN 0-471-11709-9.

• mwzwCrittografia simmetrica

• mw0qCifratura a blocchi

• mw0wCifrario a trasposizione

• mw1qCifrario a sostituzione

• mw1wFunzione booleana

• mw2qP-box

• mw2wS-box del Rijndael

Altri progetti

• Wikibooks

• Wikibooks contiene testi o manuali sulle S-Box

• mw4a(EN) A literature survey on S-Box design - Research Comments from Ciphers By Ritter, su ciphersbyritter.com.

• mw4g(EN) John Savard's "Questions of S-Box Design", su quadibloc.com.

• mw5a(EN) Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems", su securitydocs.com. URL consultato il 14 dicembre 2008 (archiviato dall'url originale il 13 maggio 2008).